\documentclass[12pt]{article}
\usepackage{xeCJK}
\usepackage[top=1in,bottom=1in,left=1.25in,right=1.25in]{geometry}

\usepackage{threeparttable}

\usepackage{mathrsfs}
\usepackage{amsmath,amsthm,amssymb}

\usepackage{color}

\usepackage{listings}
\lstset {frame=shadowbox, language=C++, basicstyle=\rmfamily\small, xleftmargin=2em,xrightmargin=2em, aboveskip=1em}

\title{User Mode Ucore Internals}
\author{茅俊杰}
\setCJKmainfont{WenQuanYi Zen Hei Sharp}

\begin{document}
\maketitle

\section{概述}
User Mode Ucore(以下简称umUcore)是一个在特定操作系统（以下称为宿主系统）下以用户态运行的模拟“操作系统”，即利用宿主系统为用户态程序提供的资源模拟一般ucore运行时的硬件支持，使ucore得以作为宿主系统的一个用户态程序运行（类似于虚拟机）。与一般的虚拟机相比，由于不存在指令翻译的问题，umUcore可以用更小的额外开销模拟ucore在硬件平台上的真实运行，但另一方面不支持ucore体系结构相关部分的调试。

\section{相关工作}
Linux也有一个用户态下运行内核的虚拟平台，称为User Mode Linux（以下简称UML）。UML由Jeff Dike从2000年开始编写，从Linux Kernel 2.6开始作为一种新的architecture合并入Linus的代码树。

对于用户态下模拟操作系统的实现，UML有三种模式：tt mode、skas3 mode和skas0 mode。目前tt mode由于skas0 mode的出现而几乎不再使用，skas3 mode需要从源码级对宿主操作系统的系统调用进行修改并重新编译，故umUcore的实现更多参考的是其skas0 mode的机制。

\section{实现简介}

以下讨论x86平台下宿主系统为Linux的umUcore的实现。

\subsection{主要工作}
对于ucore而言，关键的硬件支持包括中断与页机制，此外设备驱动也与底层硬件密切相关，对于umUcore的实现而言，关键在于如何利用宿主系统提供的资源，模拟上述的硬件支持，以统一的接口为内存管理、进程管理等提供服务。

\subsection{中断}
umUcore的外部中断通过宿主系统的信号机制加以模拟，各信号的处理例程作为相应中断的中断服务程序。目前使用的信号及其含义如下：

\begin{center}
  \begin{tabular}{ll}
    \texttt{SIGSEGV} & 模拟所有的Page Fault。\\
    \texttt{SIGVTALRM} & 模拟时钟中断。\\
    \texttt{SIGIO} & 模拟I/O设备中断，目前指键盘输入。\\
  \end{tabular}
\end{center}

\subsection{设备驱动}
目前umUcore涉及的外部设备包括磁盘（数据和Swap）、终端（字符输出）和键盘。

磁盘设备利用了宿主系统的文件操作，将外部文件作为内核的磁盘设备进行读、写操作。

终端使用了\texttt{/dev/tty}作为输出对象，所有输出的内容都写入该“文件”，最终显示在当前运行umUcore的终端上。考虑到\texttt{/dev/tty}初始时为带有缓冲的字符设备，故需要在内核初始化时利用\texttt{ioctl}系统调用进行设置，部分关键选项如下\footnote{详见termios的manual}：

\begin{center}
  \begin{tabular}{ll}
    \texttt{ISIG} & 设为1，即允许特殊字符引发信号（用于\texttt{SIGQUIT}）； \\
    \texttt{ECHO} & 设为0，即不回显输入字符；\\
    \texttt{c\_cc[V\_QUIT]} & 设为034，即\verb|Ctrl-\|会引发\texttt{SIGQUIT}；\\
    \texttt{c\_cc[V\_INTR]} & 设为0，使\verb|Ctrl-C|不会引发\texttt{SIGINT}。\\
  \end{tabular}
\end{center}

注意目前BackSpace不能正常工作（该键并不发出Erase字符010，取而代之的是Delete字符，即0177），其替代品是\verb|Ctrl-H|，此时字符会从发送序列中删除，但不会从终端上消失。

键盘输入采用异步I/O方式进行。umUcore在启动时会新建一个宿主进程阻塞地等待键盘输入，每次输入一个字符即向当前运行的umUcore进程（通过\texttt{current}全局变量确定）发送\texttt{SIGIO}信号，之后由信号处理例程完成相应的处理。

\subsection{内存}
umUcore利用内核刚启动时创建的临时文件作为其存储单元（该文件已被删除以防止内核运行时其它进程对其进行操作），以下所有提到的页的“物理地址”在umUcore中即是该页在临时文件中的偏移量。

\subsection{页机制}
页机制的模拟采用页表与宿主进程虚存结合的方式完成，其中页表完成映射与各项属性的记录，宿主进程的虚存完成实际运行时从虚地址到物理地址的映射（其实是宿主进程的页表将虚地址转换到了临时文件的相应偏移处），详细信息见Part \ref{symbolic_page}。

\subsection{进程}
umUcore采用一个主进程加一系列从属进程（这些进程均指宿主进程）的结构作为进程模拟的基础。主进程即umUcore启动时的进程，在umUcore内部实现了线程切换机制，使得在主进程中可以同时存在多个线程分时运行，这些线程包括umUcore的内核线程以及其进程的内核线程部分（关于进程的详细结构见Part \ref{symbolic_process}）；从属进程由主进程产生，作为具有相同内存管理结构（\texttt{mm\_struct}）的umUcore用户态进程的“容器”，所有用户态进程都在其对应的容器中运行，主进程在从属进程收到信号或提出系统调用请求时暂停从属进程的运行，处理相应事件，然后恢复其运行或切换另一个进程运行。

\section{\label{symbolic_page}页机制}

\subsection{一些记号}
为了无歧义地描述umUcore中页状态的变换，引入以下符号描述一条指令执行时的内存管理环境。

一个内存管理环境包括ucore当前的虚存管理结构（以下简写为vmm）$V$，ucore当前的页表$T$以及对应宿主进程的vmm$VH$，即：

\begin{tabular}{r@{\ $::=$\ }l}
  $\Sigma$ & $\langle V,T,VH \rangle$ | \texttt{ERROR}
\end{tabular}

其中\texttt{ERROR}表示访问地址出错（即访问了不允许访问的地址），便于下面讨论页操作的效果。

vmm是一个从页号$LOC$到表示该页属性的三位向量的部分映射，即：

\begin{center}
  $V$ : $LOC \rightharpoonup \langle RWE \rangle$ | $\epsilon$

  $VH$ : $LOC \rightharpoonup \langle RWE \rangle$
\end{center}

其中可读属性R、可写属性W、可执行属性E的取值范围为${0,1}$，0表示不允许，1表示允许。

页表实际是一个从虚拟地址到物理地址的部分映射，由于以下需要讨论的主要是页表中各属性位的变化及其关系(umUcore中实际上不使用页表完成地址转换)，故将$T^U$简化为从页号到页属性（由六位向量表示）的部分映射，即：

\begin{center}
  $T$ : $LOC \rightharpoonup \langle PUWADS \rangle $ | $\epsilon$
\end{center}

其中各属性取1的含义为：

\begin{tabular}{r@{\ :\ }l}
 $P$&页存在； \\
 $U$&页也可在用户态下访问； \\
 $W$&页可写； \\
 $A$&页已被访问； \\
 $D$&页已被写； \\
 $S$&页已被换出。\\
\end{tabular}

为方便起见，取已知元组或向量$X$的某特定元素$y$记为$X_y$，例如当前环境$\Sigma$中的页表记为$\Sigma_T$，取已知页号$l$在当前环境$\Sigma$的页表中的$P$属性记为$\Sigma_T(l)_P$。

\subsection{页操作对页表的影响}

umUcore中涉及的页操作包括新建、读、写、加载、换出（尝试换出该页）、复制等。定义变换$\sigma$描述页操作的影响，以下讨论各种情况下页操作前后页表$\Sigma_T$与$\Sigma'_T = \sigma_{op}(\Sigma_T, l, w)$的变化\footnote{考虑到x86的页表结构，只要可读即可执行，故以下$\Sigma_V(l)_E$无实际影响。}。记$op$代表某种页操作，$\sigma$变换的使用规则如下：

\begin{enumerate}
\item $\sigma_{op}(\Sigma, l)$ 表示在当前环境$\Sigma$下对页$l$进行操作$op$后的新环境，可能为\texttt{ERROR}；
\item $\sigma_{op}(T,l,w)$ 表示在当前页表$T$的基础上对$l$进行操作$op$后的新页表，可能为\texttt{ERROR}，$w$为vmm中该页是否可写，1表示可写；
\item $\sigma_{op}(t, w)$ 表示对当前页表项$t$（如上所述，仅考虑其属性）进行$op$操作后的新表项，可能为\texttt{ERROR}，$w$为vmm中该页是否可写，1表示可写。
\end{enumerate}

\subsubsection{内核态}
内核态的页表在系统启动完成其初始化后不再修改，其表项的属性也不作为其它操作的依据，故可以认为任何页操作对$\Sigma_T$均无影响，即$\Sigma'_T = \Sigma_T$。

\subsubsection{用户态，$l \not \in Dom(\Sigma)$或$\Sigma_V(l) = \langle 0, 0, 0 \rangle$}
此时用户态程序不允许访问$l$所对应的地址空间，因而记$\Sigma'_T =$ \texttt{ERROR}。

\subsubsection{用户态，$\Sigma_V(l) = \langle 1, 0, 1 \rangle$}
此时用户态程序只允许读$l$对应地址空间的数据，记$t = \Sigma_{T}(l)$，$t' = \sigma_{op}(t, 0)$，其对应关系列表见Table \ref{user_page_r}（空白项代表无操作，COPY项记录源页表项的变化，若无附注则目的表项与源表项的属性相同，\texttt{ERROR}代表访问错误）。

\begin{threeparttable}[!hbp]
  \begin{center}
    \begin{tabular}{c|cccccc}
      $t$ & NEW & READ & WRITE & LOAD & SWAP OUT & COPY \\ \hline
      $\langle 000000\rangle$ & $\langle 110000\rangle$ & $\langle 110100\rangle$ & \texttt{ERROR} & $\langle 110000\rangle$ & & \\
      $\langle 110000\rangle$ & $\langle 110000\rangle$\tnote{1} & $\langle 110100\rangle$ & \texttt{ERROR} & & $\langle 000001\rangle$ & $\langle 110000\rangle$ \\
      $\langle 110100\rangle$ & $\langle 110000\rangle$\tnote{1} & $\langle 110100\rangle$ & \texttt{ERROR} & & $\langle 110000\rangle$ & $\langle 110100\rangle$ \tnote{2} \\
      $\langle 000001\rangle$ & $\langle 110000\rangle$\tnote{1} & $\langle 110100\rangle$ & \texttt{ERROR} & & & $\langle 000001\rangle$ \\
    \end{tabular}
    \caption{\label{user_page_r}用户态，可读情况下页表项的理想状态转移表}
    \begin{tablenotes}
      \item[1] 需要先删除原表项。
      \item[2] 目的表项为$\langle 110000 \rangle$。
    \end{tablenotes}
  \end{center}
\end{threeparttable}

对于未出错的访问，结束后有$\Sigma'_T(l) = t'$，先不考虑NEW、LOAD等操作可能涉及的换页，用$op$表示上述页操作的任何一个，则有：

\begin{displaymath}
  \Sigma'_T(x) = \sigma_{op}(\Sigma_T, l, 0) = \left\{
  \begin{array}{lc}
    \sigma_{op}(\Sigma_T(l), 0) & if\ x=l \\
    \Sigma_T(x) & otherwise
  \end{array}
  \right.
\end{displaymath}

特别地，若$\Sigma_T = \texttt{ERROR}$或$\sigma_{op}(\Sigma_T(l), 0) = \texttt{ERROR}$，则$\sigma_{op}(\Sigma_T, l, 1) = \texttt{ERROR}$。

\subsubsection{用户态，$\Sigma_V(l) = \langle 0, 1, 1 \rangle$}
考虑到x86页表结构不支持定义一个页可写但不可读\footnote{在Linux中的mmap参数里只要指定可写或可执行，该页也同时可读}，故这里不考虑此情况。

\subsubsection{用户态，$\Sigma_V(l) = \langle 1, 1, 1 \rangle$}
此时用户态程序对$l$对应地址空间有完全的访问权限，记$t = \Sigma_{T}(l)$，$t' = \sigma_{op}(t, l, 1)$为访问后的属性，其对应关系列表见Table \ref{user_page_rw}（空白项代表出错或无操作，COPY项记录源页表项的变化，若无附注则目的表项与源表项的属性相同）。

\begin{threeparttable}[!htp]
  \begin{center}
    \begin{tabular}{c|cccccc}
      $t$ & NEW & READ & WRITE & LOAD & SWAP OUT & COPY \\ \hline
      $\langle 000000\rangle$ & $\langle 111000\rangle$ & $\langle 111100\rangle$ & $\langle 111110\rangle$ & $\langle 111000\rangle$ & & \\
      $\langle 110000\rangle$ & $\langle 111000\rangle$\tnote{1} & $\langle 110100\rangle$ & $\langle 111110\rangle$\tnote{3} & & $\langle 000001\rangle$ & $\langle 110000\rangle$ \\
      $\langle 110100\rangle$ & $\langle 111000\rangle$\tnote{1} & $\langle 110100\rangle$ & $\langle 111110\rangle$\tnote{3} & & $\langle 110000\rangle$ & $\langle 110100\rangle$\tnote{2} \\
      $\langle 111000\rangle$ & $\langle 111000\rangle$\tnote{1} & $\langle 111100\rangle$ & $\langle 111110\rangle$ & & $\langle 000001\rangle$ & $\langle 110000\rangle$ \\
      $\langle 111100\rangle$ & $\langle 111000\rangle$\tnote{1} & $\langle 111100\rangle$ & $\langle 111110\rangle$ & & $\langle 111000\rangle$ & $\langle 110000\rangle$ \\
      $\langle 111010\rangle$ & $\langle 111000\rangle$\tnote{1} & $\langle 111110\rangle$ & $\langle 111110\rangle$ & & $\langle 000001\rangle$ & $\langle 110000\rangle$ \\
      $\langle 111110\rangle$ & $\langle 111000\rangle$\tnote{1} & $\langle 111110\rangle$ & $\langle 111110\rangle$ & & $\langle 111010\rangle$ & $\langle 110000\rangle$ \\
      $\langle 000001\rangle$ & $\langle 111000\rangle$\tnote{1} & $\langle 111100\rangle$ & $\langle 111110\rangle$ & & & $\langle 000001\rangle$ \\
    \end{tabular}
    \caption{\label{user_page_rw}用户态，可读可写情况下页表项的理想状态转移表}
    \begin{tablenotes}
      \item[1] 需要先删除原表项。
      \item[2] 目的表项为$\langle 110000 \rangle$。
      \item[3] 可能需要复制页（不涉及页表项的额外变化）。
    \end{tablenotes}
  \end{center}
\end{threeparttable}

与只读权限下的访问相同，访问结束后有$\Sigma'_T(l) = t'$，先不考虑NEW、LOAD等操作可能涉及的换页，则有：

\begin{displaymath}
  \Sigma'_T(x) = \sigma_{op}(\Sigma_T, l, 1) = \left\{
  \begin{array}{lc}
    \sigma_{op}(\Sigma_T(l), 1) & if\ x=l \\
    \Sigma_T(x) & otherwise
  \end{array}
  \right.
\end{displaymath}

特别地，若$\Sigma_T = \texttt{ERROR}$或$\sigma_{op}(\Sigma_T(l), 1) = \texttt{ERROR}$，则$\sigma_{op}(\Sigma_T, l, 1) = \texttt{ERROR}$。

\subsection{页操作对宿主进程vmm的影响}
对于一个允许访问的页$l$，$\Sigma_{VH}(l)$完全由$\Sigma_T(l)$决定，规则如下：
\begin{enumerate}
\item $ \Sigma_{VH}(l)_R = \Sigma_{VH}(l)_E$ 恒成立；
\item $ \Sigma_{VH}(l)_R = 1 \Leftrightarrow \Sigma_T(l)_A = 1$；
\item $ \Sigma_{VH}(l)_W = 1 \Leftrightarrow \Sigma_T(l)_D = 1 \land \Sigma_T(l)_A = 1$。
\end{enumerate}
记通过以上规则从页表项$t$到vmm表项$v$的映射为$\varphi$，特别地，$\varphi(\texttt{ERROR}) = \texttt{ERROR}$。

\subsection{页操作对内存管理环境的影响}
综合以上讨论，$\Sigma' = \sigma_{op}(\Sigma, l)$定义如下：

\begin{enumerate}
\item $\Sigma'_V = \Sigma_V$；
\item $\Sigma'_T = \sigma_{op}(\Sigma_T, l, \Sigma_V(l)_W)$；
\item $\Sigma'_{VH}(x) = \left\{
\begin{array}{lc}
  \varphi(\Sigma'_T(l)) & if\ x=l \\
  \Sigma_{VH}(x) & otherwise
\end{array}
\right.$。
\end{enumerate}

特别地，若$\Sigma = \texttt{ERROR}$或$\sigma_{op}(\Sigma_T, l, \Sigma_V(l)_W) = \texttt{ERROR}$，则$\Sigma' = \texttt{ERROR}$。

\subsection{\label{proving}允许执行与可执行的关系}
在umUcore中，允许执行的条件是vmm（即$\Sigma_V$）中相应表项设有相应的权限，而可执行的条件是宿主进程的vmm（即$\Sigma_{VH}$）中相应表项设有相应的权限。设当前内存管理环境为$\Sigma$，当前访问页为$l$，定义如下判断：

\vspace{10pt}
\begin{tabular}{|l|l|}
  \hline
  $\Sigma \vdash l \texttt{ re}$ & 读页可执行（Read Executable）\\
  $\Sigma \vdash l \texttt{ we}$ & 写页可执行（Write Executable）\\
  $\Sigma \vdash l \texttt{ rp}$ & 允许读页（Read Permitted）\\
  $\Sigma \vdash l \texttt{ wp}$ & 允许写页（Write Permitted）\\
  \hline
\end{tabular}
\vspace{10pt}

各判断的定义为：

\begin{center}
  \begin{tabular}{c}
    $\Sigma_V(l)_R=1$ \\ \hline
    $\Sigma \vdash l \texttt{ rp}$
  \end{tabular}
  \begin{tabular}{c}
    $\Sigma_V(l)_W=1$ \\ \hline
    $\Sigma \vdash l \texttt{ wp}$
  \end{tabular}
\end{center}

\begin{center}
  \begin{tabular}{c}
    $\Sigma_0=\Sigma$ \\
    $\Sigma_{k+1} = \sigma_{READ}(\Sigma_k, l)$  \\
    $(\Sigma_{\infty})_{VH}(l)_R = 1$ \\ \hline
    $\Sigma \vdash l \texttt{ re}$
  \end{tabular}
  \begin{tabular}{c}
    $\Sigma_0=\Sigma$ \\
    $\Sigma_{k+1} = \sigma_{WRITE}(\Sigma_k, l)$  \\
    $(\Sigma_{\infty})_{VH}(l)_W = 1$ \\ \hline
    $\Sigma \vdash l \texttt{ we}$
  \end{tabular}
\end{center}

则在任何情况下（即对任何合法的$\Sigma$），应保证：

\begin{enumerate}
\item $\Sigma \vdash l \texttt{ re} \Leftrightarrow \Sigma \vdash l \texttt{ rp}$
\item $\Sigma \vdash l \texttt{ we} \Leftrightarrow \Sigma \vdash l \texttt{ wp}$
\end{enumerate}

严格来说，应该证明基于上述定义的变换，对于任何$\Sigma$都应该能保证以上两点。具体证明此处从略。

\subsection{\label{mm_impl}实现上的问题}
上面讨论的六项页操作可以分为三类：NEW、LOAD、COPY通过系统调用等方法由用户态进程主动请求内核执行，SWAP OUT由内核在执行过程中在适当时机完成，READ、WRITE允许用户不经过内核直接进行。由于前两类有内核的介入，在完成操作的同时可以同时修改页表以完成上述变换，与底层的体系结构没有直接关系。

然而，READ、WRITE对应的变换在x86架构上由硬件完成（主要是设置访问位和脏位，只有COW通过页保护机制产生中断后由内核完成），但在um架构下，相应的位并不能直接交给硬件，必须通过某种机制让内核在用户进程第一次读或写某页时介入并修改相应属性。目前umUcore采用的方法是在页$l$被读之前，$\Sigma_{VH}(l)_R = 0$，在$l$被写之前，$\Sigma_{VH}(l)_W=0$。这样当该页被访问时，由于$\Sigma \vdash l \texttt{ re}$或$\Sigma \vdash l \texttt{ we}$不成立，将引起\texttt{SIGSEGV}信号（即umUcore中用于模拟Page Fault的信号），在信号服务例程中即可对页表进行需要的修改并重新映射该页，使之后的相同访问不再产生信号。（以上也是引入$\varphi$的原因）

实现该机制的另一个必要条件是在\texttt{SIGSEGV}发生后，内核有途径知道发生缺页异常的地址以及期望对该地址进行的操作。由于linux，缺页地址可以通过调用ptrace系统调用获得的siginfo中直接获得，但siginfo中对期望操作的标识不够明确（只包含\texttt{MAPERR}表示无映射存在，\texttt{ACCERR}表示映射存在但权限出错，并未指出是读还是写）。UML中的处理方案是由监控线程向容器进程发送\texttt{SIGSEGV}信号，令容器进程在初始化时注册的\texttt{SIGSEGV}处理函数通过sigcontext获得更详细的信息。而在umUcore按此方法进行实现时，遇到的问题是容器进程的信号处理仅在第一次调用时能正常工作，之后再向该进程发送\texttt{SIGSEGV}，即重新调用默认的处理过程。

目前的解决方案是仍然使用siginfo，同时通过当前对应页表项的状态猜测当前的访问是读还是写：若页表项的Accessed Bit没有置位，则以当前为读操作进行处理，否则按照当前为写操作进行处理。这种方式能够保证正确性，但在对一个尚未访问过的页进行写操作时，将会多产生一次缺页中断，在运行效率上有所损失。

需要指出的是，一个页的写可执行不能仅仅靠页表的Dirty Bit确定。一个反例是在$\Sigma_T(l) = \langle 111010 \rangle$，同时当前需要读或写该页时，有$\varphi(\langle 111010 \rangle) = \langle 010 \rangle$，由于x86体系并不支持设置某页为可写但不可读，所以此时实际上有$\Sigma \vdash l \texttt{ re}$（这与定义相悖），因而该访问不会产生\texttt{SIGSEGV}，应该设置的$\Sigma_T(l)_A$不会被置为1。为了在读、写该页时内核能收到通知，页只有在Accessed Bit和Dirty Bit均置位的情况下才能标记为写可执行。

\section{\label{symbolic_process}进程模拟}
从宿主系统的角度而言，umUcore是一个多进程的应用程序，包括最开始运行的主进程$P_M$（模拟内核运行环境），用于完成异步IO操作的辅助进程$P_H$，以及作为umUcore进程“容器”的容器进程$P_C$（模拟用户运行环境）。在$P_M$内部，umUcore通过实现简单的用户态线程机制，一方面模拟所有内核线程$T$（到目前为止仅有$T_{IDLE}$和$T_{KSWAPD}$），另一方面为每一个umUcore的进程$\mathscr{P}$配置一个监控线程，用于完成其中断、系统调用的模拟。

基于以上符号，umUcore的进程模拟图示如Figure \ref{proc_struct}。

\begin{figure}[!hbp]
\begin{verbatim}
       +------------------------------+   +-----+
       | P_M                          |---| P_H |
       |  +---+  +---+  +---+  +---+  |   +-----+
       |  | T |  | T |  | T |  | T |  |
       |  +---+  +---+  +---+  +---+  |
       |           |      |      |    |
       +-----------|------|------|----+
                   V      V      V
                   +-------+  +-----+
                   |  P_C  |  | P_C |
                   +-------+  +-----+
\end{verbatim}
\caption{\label{proc_struct}umUcore进程模拟结构}
\end{figure}


\subsection{主进程$P_M$}
$P_M$由宿主系统的Shell创建，用于控制umUcore的整体运行。从运行过程的角度，在不同阶段其功能也不完全相同。

\subsubsection{Bootloader阶段}
umUcore包括两个二进制文件：bootloader和kernel。

Bootloader为宿主机上实际可运行的程序，完成创建模拟内存、打开文件系统的映像文件、加载kernel、清空进程的虚地址空间的工作，最后把控制权交给加载到内存的kernel。Bootloader需要指定的参数如下：

\begin{tabular}{l@{\ \ }l}
  \verb|--kernel=<path>| & 指定内核文件的路径为path，无默认值；\\
  \verb|--memsize=NUM| & 指定模拟内存大小为NUM，NUM可用单位K、M，默认值为128M；\\
  \verb|--disk=<path>| & 指定文件系统映像的路径为path，无默认值；\\
  \verb|--swap=<path>| & 指定交换分区映像的路径为path，无默认值。
\end{tabular}

注意所有无默认值的参数必须给定，否则无法正常运行，实际应用中建议使用\verb|make run|运行umUcore。

当bootloader完成上述工作并将控制权交给kernel时，$P_M$的虚地址空间结构见Figure \ref{pm_space}，这样在kernel执行时其面对的地址空间与在其它架构下基本类似（差别在指定地址边界的宏），有利于之后更多地利用已有代码实现内存管理。

\begin{figure}[!hbp]
\begin{verbatim}
+------------------------------+
|                              |
|       Host Kernel Area       |
|                              |
+------------------------------+ <---------- HOSTBASE
|        ** Invalid **         |
+------------------------------+ <---------- KERNTOP
|                              |
|   Remapped Physical Memory   |
|                              |
+------------------------------+ <---------- KERNBASE / USERTOP
|                              |
:                              :
|       ~~~~~~~~~~~~~~~        |
:                              :
|                              |
+------------------------------+ <---------- USERBASE
|        ** Invalid **         |
+------------------------------+ <---------- 0
\end{verbatim}
\caption{\label{pm_space}主进程$P_M$的虚地址空间}
\end{figure}

此时模拟内存的内容包括一些全局信息（如映像文件的描述符等）、内核栈、内核代码以及可用区域，详见\verb|arch/um/include/memlayout.h|。

\subsubsection{初始化阶段}
Kernel开始运行后，与在其它架构下相同，首先进行各方面的初始化工作，除了硬件初始化需要另写代码进行模拟以外，其它部分大都为ucore内部数据结构的初始化，与架构无关，可直接使用已有实现。

\subsubsection{运行阶段}
当初始化工作结束、内核产生用户进程后，$P_M$的工作主要是基于用户态线程，模拟内核线程以及进程调度。模拟内核线程只需在$P_M$中运行对应线程即可，进程调度的问题涉及用户进程的结构，详后述。

\subsection{用户进程}
在umUcore中，用户进程与内核线程的不同之处在于用户进程并不真正在$P_M$中运行，而是运行在内核分配给它的宿主容器进程中（注意，一个容器进程可能分配给多个umUcore的轻量级进程），其需要内核参与的部分则由主进程中相应的监控线程转译执行，即对umUcore而言逻辑上的“进程”$\mathscr{P}$由一个$P_M$中的监控线程$T$和分配给它的容器进程$P_C$，之后为了描述方便，用$\mathscr{P}_T$表示$\mathscr{P}$的监控线程，$\mathscr{P}_P$表示其容器进程。

\subsubsection{容器进程的虚地址空间}
从宿主进程来看，容器进程的虚地址空间如Figure \ref{pc_space}所示。

\begin{figure}[!hbp]
\begin{verbatim}
+------------------------------+
|                              |
|       Host Kernel Area       |
|                              |
+------------------------------+ <---------- HOSTBASE
|        ** Invalid **         |
+------------------------------+ <---------- KERNBASE / USERTOP
|                              |
:                              :
|       ~~~~~~~~~~~~~~~        |
:                              :
|                              |
+------------------------------+ <---------- USERBASE
|        ** Invalid **         |
+------------------------------+ <---------- STUB_END
|      ** Stub Stack **        |
+------------------------------+ <---------- STUB_DATA
|       ** Stub Code **        |
+------------------------------+ <---------- STUB_CODE
|        ** Invalid **         |
+------------------------------+ <---------- 0
\end{verbatim}
\caption{\label{pc_space}容器进程的虚地址空间}
\end{figure}

其中Stub Code为转译部分系统调用所需要的代码；Stub Stack保存转译代码需要的参数。可以看到，在容器进程中除了转译相关的数据外（这些数据在每次转译前写入有效值，执行完当前转译后即不再需要），不包含任何内核的代码或数据，因而用户进程不可能访问到内核相关的任何部分。

\subsubsection{\label{createUser}用户进程的创建}
创建用户进程的工作可以由\verb|do_execve|和\verb|do_fork|完成。相比于i386的ucore而言，在umUcore中创建用户进程在维护ucore内部公共数据结构方面完全相同，而原先切换页表的工作则代之以创建、分配容器进程。

需要提及的是\verb|do_execve|和\verb|do_fork|的实现。实际上创建容器进程是\verb|do_execve|的最后一步，而之前已经调用\verb|load_icode|将代码与相关数据载入内存，这时这些映射临时存在于主进程中（这是两个需要在主进程的用户地址空间进行映射的情况之一，另一个参见\ref{accessToUser}）。由于\verb|do_execve|必然创建容器进程，且创建过程实际是调用宿主系统的\verb|fork|，故主进程的映射将完全复制给容器进程，之后只要主进程将用户空间刷空，容器进程将内核部分刷空即可。与之不同的是，\verb|do_fork|创建的容器进程的用户空间全空，其需要的代码与数据是通过发生缺页异常之后才映射到其虚存空间的，此处也为了简单期间引入了许多可以避免的缺页中断。

\subsubsection{用户进程的运行}
对于一个umUcore的进程$\mathscr{P}$而言，当它从内核获得运行资格后，首先启动$mathcsr{P}_T$（一般在函数\verb|userspace|中，参见\verb|arch/um/kernel/process.c|）。$\mathscr{P}_T$恢复$\mathscr{P}_P$的寄存器，启动$\mathscr{P}_P$的执行，本身则等待$\mathscr{P}_P$发生需要截获的事件（中断或系统调用）。

当$\mathscr{P}_P$发生事件后，$\mathscr{P}_T$得到通知，保存$\mathscr{P}_P$的当前寄存器，检查事件类型并做出相应的处理，具体处理过程如下：

\begin{tabular}{l@{\ \ }l}
  Page Fault (SIGSEGV) & 获得中断原因，调用缺页中断服务例程\verb|do_segv|； \\
  Timer (SIGVTALRM) & 调用时钟中断服务例程\verb|vtimer_handler|； \\
  AIO (SIGIO) & 调用异步IO中断服务例程\verb|io_handler|； \\
  除零操作 (SIGFPE) & 推出userspace循环，中止进程； \\
  系统调用 (SIGTRAP + 0x80) & 取消该调用在宿主系统上的执行，\\ 
  & 获得系统调用信息，调用syscall完成转译。
\end{tabular}

处理结束后若需要重新调度，调用\verb|schedule|，否则恢复$\mathscr{P}_P$的寄存器并再次启动$\mathscr{P}_P$执行。

\subsubsection{用户进程的结束}
用户进程的收尾工作由\verb|do_exit|完成，其对于内部数据结构的修改与已有实现完全相同，此外还多了在适当时候销毁容器进程的工作。在容器进程描述符\verb|host_container|（参见\verb|arch/um/include/arch_proc.h|）中存有该容器当前容纳的用户进程数，每次结束用户进程时该计数器减1，当计数器归零时释放该容器进程。

\subsection{进程调度}
从上面的描述中可以看到，对于内核而言无论是内核线程还是用户进程，其上下文切换本质上都是线程切换（只是切换到的时不同类的线程而已），在umUcore中利用\verb|setjmp|、\verb|longjmp|（与C库中相同）完成。

\subsection{\label{accessToUser}内核服务对用户数据的访问}
对于umUcore而言，内核服务（中断或系统调用）由监控线程转译并完成于$P_M$中，而其涉及的用户态数据则映射在相应的$\mathscr{P}_P$中，二者在宿主系统上是不同的进程，因而不像在其它架构下可以对用户数据进行直接访问，需要提供另一种访问数据的机制，既能保证数据的正确性，又能对页表产生应有的影响。

在目前的实现中采用一种比较简单的方法完成这一点：第一步利用Stub Code对需要访问的页进行相应操作，完成页表的修改；第二步通过查找页表中相应页的“物理”地址（即在模拟内存里的偏移量），直接访问该位置的数据。

对于大多数情况，上述机制虽然引入了多次地址合法性检查，但可以完成预定的任务，例外情况只有一个：\verb|sys_getcwd|。该函数的第一个参数是用于填入当前目录绝对路径的用户态缓存空间，而在其具体实现中则将该空间作为IO Buffer直接读写。考虑到修改具体实现太过麻烦，所以采用在处理系统调用时暂时将该缓存映射到主进程，返回前再取消该映射的方法。这种方法的潜在问题是要求整个\verb|sys_getcwd|的执行过程不能被打断，否则若在执行过程中另一个进程调用\verb|sys_fork|或\verb|sys_execve|，主进程用户空间中的用户缓存映射很可能被覆盖，导致运行结果出错。目前ucore在内核态下不会被打断，\verb|sys_getcwd|的执行过程也不会主动放弃执行，因而暂时不存在上述问题发生的可能。

\section{体系相关的结构与函数集}
以下罗列umUcore体系相关与无关的接口层函数（主要与i386实现比较），不考虑测试函数。

\subsection{内存管理}
内存管理涉及的函数主要位于\verb|arch/um/mm/pmm.c|中，虚存相关的则在\verb|arch/um/mm/vmm.c|中。

\subsubsection{初始化}
主要为\verb|pmm_init|，完成页机制的初始化工作。umUcore不存在启动页机制、页表重映射等问题，相比于i386的实现少了相关内容。

\subsubsection{页映射操作}
主要为\verb|tlb_flush|、\verb|tlb_invalidate|，完成某一页在某一进程中的映射工作。由于ucore中不同的\verb|mm_struct|有不同的页表，因而只有同一线程组内的轻量级进程，其\verb|mm->pgdir|才相同；另一方面同一线程组的所有轻量级进程均分配在同一个容器进程中，故\verb|pgdir|与容器进程有一一对应关系，在页映射操作中指定了页表的同时，也指定了需要完成映射操作的宿主进程。\verb|tlb_flush|和\verb|tlb_invalidate|的第一步都是通过\verb|pgdir|参数确定需要完成映射的宿主进程，然后调用宿主系统的系统调用完成相应工作，前者修改或载入某一映射，后者取消某一映射。

相比于i386而言，umUcore的页映射无论加载、修改还是取消都必须通过宿主系统调用才能实现，仅仅修改页表项毫无用处，这也是在原来只有\verb|tlb_invalidate|的基础上增加\verb|tlb_flush|的原因，同时在非体系相关部分在不同场合调用了不同的接口。对于i386的情形，只需将二者等同即可。

\subsubsection{打印页表}
主要为\verb|print_pgdir|及其相关函数。由于umUcore中很难实现i386版本中的页表重映射，因而目前采用最简单的方法，利用两个函数分别处理页目录和页表，逐次遍历、打印。

\subsubsection{虚存管理}
包括\verb|copy_to_user|、\verb|copy_from_user|和\verb|copy_string|三个函数。之前提到，内核服务无法直接访问用户数据，而许多系统调用的参数中都包含用户空间的指针，作为复杂参数的地址或保存调用结果。在i386的实现中，以上三个函数用于在访问给定地址前检查该地址是否有效（根据vmm），而在umUcore中，上述函数进行更复杂的操作，包括合法性检查、页表修改以及数据复制。同时，在原有的实现中在同一个函数里一旦调用过上述函数，之后对相同地址的访问即直接以指针操作进行（不必再进行合法性检查），但对于umUcore而言，每次相关操作都必须通过上述接口进行。目前修改了相关指针操作为对应函数调用，对于i386的运行而言不会影响正确性，但会降低效率。

\subsection{进程管理}
一般位于\verb|arch/um/kernel/proc.c|，从功能上，主要分为以下几类：

\begin{enumerate}
\item 体系相关数据结构：主要是\verb|alloc_proc|。\\
  由于PCB中有体系相关的数据，需要一个函数对其进行初始化（公共部分目前尚未被提取出来）。
\item 线程/进程创建或销毁相关：包括\verb|kernel_thread|、\verb|copy_thread|、\verb|init_new_context|、\verb|kernel_execve|、\verb|do_execve_arch_hook|、\verb|de_thread_arch_hook|等。\\
  这些函数通常直接负责线程/进程的创建，由于不同体系结构下创建进程的过程不尽相同，因而将其抽取出来，放到体系结构相关目录下实现。
\item 内核调用进程创建函数相关：主要为\verb|kernel_execve|。\\
  由于umUcore中不必要通过中断调用\verb|do_execve|，因而实现比i386简单。
\end{enumerate}

从实现形式上，主要分为：
\begin{enumerate}
\item 函数整体重新实现：所有无hook后缀的函数均在原先i386中已有，现在放到体系相关目录中，让每个体系分别进行实现。
\item 嵌入钩子：带有hook后缀的是在原先i386基础上在某些点加入的供体系相关实现完成其特殊功能的函数，一般这些函数的i386实现目前为空。
\end{enumerate}

\subsection{其它}
除了上述两部分构成体系相关接口的主体以外，需要各体系结构各自实现的还包括外设驱动、原子操作、中断启闭等需要硬件支持的部分。

\section{目前尚存在的缺陷}
目前的实现有许多地方仍然十分“丑陋”，在今后的工作中应该首先考虑优化，罗列如下：

\begin{enumerate}
\item 证明目前所采用的页表处理方案在任何情况下都与在其它平台上有相同的行为。（详见\ref {proving}）
\item 解决缺页中断的信息提取问题。（详见\ref {mm_impl}）
\item 考察\verb|do_fork|是否应该在容器进程运行前主动映射代码与数据。（详见\ref {createUser}）
\item 对于用户调用\verb|execve|的情况，在可能的情况下重用已有的容器进程，而不是先杀掉已有的，再创建一个新的。
\item 
\end{enumerate}

\section{关于调试}

使用gdb对umUcore进行调试时，有时会发生断点无效的情况，例如下面这段代码（参见debug分支\verb|arch/um/kernel/process.c|的\verb|clone|函数）：

\begin{lstlisting}
  dummy1 ();
  int ret = syscall0 (__NR_fork);
  dummy2 ();
\end{lstlisting}

其中\verb|dummy1|、\verb|dummy2|均为空函数，syscall0为宿主系统\verb|int $0x80|的包装。使用gdb对其调试，分别在\verb|dummy1|、\verb|dummy2|处设置断点，发现\verb|dummy1|可以正常停下，但\verb|dummy2|的断点无法使之停止，包括执行流在该\verb|fork|系统调用之后的所有断点均无法正常工作。另一方面，若通过单步执行走到\verb|dummy2|，则之后的断点又能起效。上述现象在gdb 6.8.50.20090302-40.fc11、gdb 7.2.90.20110525-38.fc15中均有发生，目前未知其原因。

通过查看UML官方对于Kernel Hack的文档，发现对于UML而言这种断点失效的问题同样存在，J.Dike认为是gdb的bug，其提出的解决方案是在需要调试的代码附近加入下述循环：

\begin{lstlisting}
  while (debug);
\end{lstlisting}

在运行时\verb|debug|初始化为1，当程序进入循环后用gdb中断执行，查看需要的信息，之后设置debug为0，继续执行即可。

\end{document}
